package com.buddy.learn.algorithm.simple;

import java.util.*;

/**
 * 问题: 给出一个包含括号和小写英文字符的字符串。
 * 去掉无效（无法匹配组成整对的括号）的字符左括号'('或者右括号")"，
 * 使得输出的结果字符串仅包含有效的字符(成对的括号和英文字符)。 样例如下
 * Examples)
 * Input: s = "h)u(i)xiaoer"
 * Output: "hu(i)xiaoer"
 * Expectation) O(N) O(N)
 * Entry)
 * Edge cases)
 * Input: s = "hu((i(x(i(ao(er"
 * Output: "huixiaoer"
 */
public class StringValid {

    private static String minRemoveToMakeValid(String str) {
        Set<Integer> invalidIndexes = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                stack.push(i);
            } else if (str.charAt(i) == ')') {
                if (stack.empty()) {
                    invalidIndexes.add(i);
                } else {
                    stack.pop();
                }
            }
        }
        while (!stack.empty()) {
            invalidIndexes.add(stack.pop());
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (invalidIndexes.contains(i)) {
                continue;
            }
            sb.append(str.charAt(i));
        }
        return sb.toString();

    }

    public static void main(String[] args) {
//        String s = "hu((i(x(i(ao(er";
//        String s = "lee(t(c)o)de)";
        String s = "lee(t(c)o)de)";
        System.out.println(minRemoveToMakeValid(s));
    }
}
